"""
https://leetcode.cn/problems/binary-tree-postorder-traversal/

145. 二叉树的后序遍历
简单
相关标签
premium lock icon
相关企业
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

 

示例 1：

输入：root = [1,null,2,3]

输出：[3,2,1]

解释：



示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

解释：



示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

 

提示：

树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100
 

进阶：递归算法很简单，你可以通过迭代算法完成吗？


"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
from typing import List, Optional
from tree_node import TreeNode,build_tree_node


class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:

        res=[]
        # 先非空判断
        if not root:
            return res

        # 使用temp作为节点遍历缓冲区
        temp=[root]
        while temp:
            head=temp.pop()
            res.append(head.val)
            if head.left:
                temp.append(head.left)
            if head.right:
                temp.append(head.right)
            

        # print(res)

        return res[::-1]

if __name__=='__main__':
    """
    1
    2                       3
    4               5       None    8
    None    None    6   7           9

    res=[4,6,7,5,2,9,8,3,1]
    reverse=[1,3,8,9,2,5,7,6,4]
    """
    arr=[1,2,3,4,5,None,8,None,None,6,7,9]
    root=build_tree_node(arr)

    s=Solution()
    res=s.postorderTraversal(root)
    print(res)